1. Field of the Invention
This invention relates to computer-generated graphics and interactive display systems in general, and, in particular, to the generation of three-dimensional imagery using an efficient and compact form.
2. Description of the Related Art
The use of 3D imagery, whether displayed on a screen or in virtual reality goggles, is becoming increasingly important to the next generation of technology. Besides CAD/CAM (Computer Aided Design/Computer Aided Modelling), 3D imagery is used in videogames, simulations, and architectural walkthroughs. In the future, it may be used to represent filing systems, computer flowcharts, and other complex material. In many of these uses, it is not only the image of a 3D model that is required, but also the ability to interact with the image of the 3D model.
The process of creating and displaying three-dimensional (3D) objects in an interactive computer environment is a complicated matter. In a non-interactive environment, 3D objects require memory storage for the shape, or geometry, of the object depicted, as well as details concerning the surface, such as color and texture. However, in an interactive environment, a user has the ability to view the 3D object from many angles. This means that the system has to be able to generate the images of geometry and surface details of the 3D object from any possible viewpoint. Moreover, the system needs to generate images from these new viewpoints quickly, in order to maintain the sensation that the user is actually interacting with the 3D object.
As an example, consider viewing a 3D model of a house on a computer system with a monitor and a joystick. Although you may be viewing it on the flat computer screen, you will see the shape of the house, the black tiles on the roof, the glass windows, the brick porch, etc. But if you indicate xe2x80x9cwalk to the sidexe2x80x9d by manipulating the joystick, the viewpoint on the screen shifts, and you begin to see details around the side corner of the house, such as the aluminum siding. The system needs to keep up with your manipulations of the joystick, your xe2x80x9cvirtual movement,xe2x80x9d in order to provide a seamless, but continuously changing image of the 3D object, the house. So the system needs to redraw the same object from a different perspective, which requires a large amount of memory and a great deal of processing.
The problem of memory usage becomes even more acute when in a networked environment, where the image is being shown on a client system, while the original 3D object information is stored on a server. The client display system will have to receive the 3D object information over a communication link, thereby slowing down the process. In most cases, a compromise will have to be made between the interactive speed, how quickly the display will redraw based on user input, and the accuracy of the 3D object, how many details can be recalculated with each change in perspective. Although the following discussion will assume a networked environment, the problems addressed are also applicable to stand-alone computer systems, since an analogous situation exists between the hard drive (server) and the local memory (client) in a computer.
Before addressing the memory and processing problems, a brief discussion of 3D imaging is in order. As indicated above, the features of 3D objects can be separated into geometry, the shape and volume of the object, and surface details, such as texture, color, and shading. The first issue is how these two attributes, geometry and surface details, are stored and transmitted. The storage of geometry involves the description of the various edges and vertices of the object in 3D space. One way to speed the network time of transmitting and displaying a 3D object is to simplify the geometry, but this can make it hard to represent the original surface information on the reduced geometry, as the vast majority of simplification algorithms use only a geometric approximation and ignore the importance of surface details. A technique such as xe2x80x9ctexture mappingxe2x80x9d [Blinn] maps an image of the rendered object onto the simplified geometry, but it is difficult to create and map images onto a surface of arbitrary topology. Furthermore, the corresponding texture coordinates would have to be sent along with the model, which would increase the transmission load.
Texture mapping is one of a class of techniques called xe2x80x9cimage-based rendering,xe2x80x9d where an image of the surface details are xe2x80x9crenderedxe2x80x9d for each new perspective on the 3D object. Every time the user moves around the 3D object, a new surface image must be xe2x80x9crenderedxe2x80x9d from the new perspective. The image of surface details is taken and stored in various ways. One approach, which is used in texture mapping, is to break the surface of the 3D object into polygons, render every surface polygon as a small image, and then assemble all the images into a large montage that acts as a single texture image for the entire surface [Cignoni98]. Each polygon would then appear fully rendered and without any occlusion somewhere in the montage image, and the corresponding texture coordinates of the polygon corners would be well-defined. Occlusion occurs when some surface details are blocked from the user""s perspective. Also in this approach is a method that packs the images into the montage efficiently to minimize wasted space in the texture image.
There are other approaches to taking a surface detail image. A single texture image of an object can be created by doing a xe2x80x9cflyoverxe2x80x9d of the 3D object. This is equivalent to passing a camera over every surface of the object and taking pictures either continuously, creating one large seamless image, or discretely, creating multiple images corresponding to coverage of the entire 3D object.
Some image-based rendering techniques use these surface detail images directly as hardware texture maps [Cignoni98, Rademacher, Foran98, Erdahl97, Jackson96]; in other words, they use one or more images to completely describe the texture of the 3D object from any perspective the user may take. Others rely on data structures and algorithms that are implemented in software [Harashima98, Oliveira98, Oliveira99]; meaning that new perspectives are created or interpolated from image data by computer processing. Furthermore, some approaches are optimized for creating as realistic view as possible from a finite set of images, while others seek a compromise between accuracy and interaction speed.
There are many problems of memory usage, data transmission and excessive processing when employing the above techniques. For instance, the image-based rendering techniques that rely extensively on software algorithms to perform elaborate operations during every change of viewpoint are inapplicable to CAD/CAM and related applications that demand both high performance and high accuracy. This is even more of a problem in client-server applications in which the client may be much less powerful than the server machine. For the rest of this application, we will focus on texture mapping as the best technique for a client-server application.
When using texture mapping over a client-server/networked system, there is the need to send additional information such as texture coordinates, details, and color along with the geometry. To reduce bandwidth requirements it is important to send as little data as possible while still allowing the client to reconstruct the scene. However, this is a problem with complex rendering processes that don""t reduce to simple 2D renderings of a 3D object with a given viewpoint. Complex rendering requirements will more tightly couple the process that creates the viewable geometry with the process that renders the images, which is inappropriate, for example, when the creation process is performed on the server and the rendering process is performed on the client. Thus, in a client-server system, multiple 2D renderings or multiple texture maps of the 3D object are preferable.
When using the polygon method of texture mapping, multiple images are used to represent the surface of an object at the same time. In this situation, any difference in rendering parameters between images may result in a discontinuity between regions that can stand out as a disturbing artifact. Surfaces that do not appear seamless may be hard to interpret because the eye is drawn to the abrupt changes in surface characteristics rather than the actual features on the surface.
If, in a client-server system, the server performs the original rendering, and transmits it to the client, the client is stuck with the conditions of the original rendering. For instance, if a server renders the 3D object with a light source, resulting in shading, the client is unable to change the shading on the renderings it receives from the server. The inability of the client to view the object under different lighting and shading conditions may limit the applicability of the technique, particularly when multiple objects rendered under different conditions are collected in a single scene that has a different type of lighting.
When it is important to view the facets of a model, and yet have the client display simplified geometry, there is a fundamental problem in showing individual surface details of the original geometry using only simplified geometry. This is particularly a problem when showing shading on the facets, since if the lighting is done on the client side there is no way to subdivide a polygon into the polygons in the original model.
An object of this invention is to provide an improved system and method for representing a 3D model with surface features in a compact form.
Another object of this invention is to provide a system and a method for representing a 3D model with surface features in a compact form for rapid transmission over a network and/or for storage in computer memory.
Another object of this invention is to provide a system and a method for representing a 3D model with one surface texture at a time, thus eliminating discontinuities in surface features between regions of the 3D model.
Another object of the invention is to provide a system for interactively viewing a 3D model in an efficient manner using simplified geometry while displaying the appearance of the original model using the original surface features, including original connections and shading.
Another object of the invention is to enable a client to recreate a 3D model with a minimum of transmitted information across a network, particularly without the need to receive texture coordinates to map the images onto the geometry of the model.
To accomplish the above and other objects, a server renders a 3D model, described using geometry and surface features, from a number of viewpoints. These image renderings, or xe2x80x9ccamera views,xe2x80x9d contain the original detailed facets of the original model on the server. The data concerning the xe2x80x9ccamera positionxe2x80x9d of each viewpoint is also saved with each xe2x80x9ccamera view.xe2x80x9d The geometry of the original model is simplified to reduce the amount of information that needs to be sent across the network.
The simplified model, the rendered images, and the camera orientations are sent to a remote client that dynamically texture maps the best image based upon the current view direction. A pre-processing stage determines which portions of the model""s geometry are occluded from a given view direction and colored accordingly, to indicate that the texture information for these portions are invalid. Because there are multiple texture maps for the same model, a given spot on the model is typically depicted in more than one texture map. As the object is rotated to different view directions, the texture map changes, giving the impression that the entire object has been texture mapped.
By separating the pure geometrical component of the model from all the data and surface features that contribute to its rendered appearance, the client need only be able to drape a texture onto a geometric mesh to recreate the rendered appearance on the client. The server need only create a few images of the model from a view camera direction, and the client need only receive the (possibly simplified) geometry of the model without any additional surface data or annotations that are represented in the texture images. The client is both thin and generic, because all the specifics of rendering a model remain the job of the server application.